package gold.gold03;

import java.util.ArrayList;
import java.util.List;

/**
 * 这种场景经常可以遇到。
 * 果然还是需要对集合多了解, 不同类的方法。
 * 如果用set和list相互转换, 可能会省一些判断。
 * 注意如果子函数返回的是null, 是不能用addAll来处理的, 编译不报错, 但是运行不可以。
 * 注意List长度是.size()不是.length, 后者是int[]用的。
 */
public class S0804幂集_集合的所有子集 {
    // 87, 这种方式其实有点像位运算了。
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null) return null;
        int lenCount = nums.length;
        System.out.println(lenCount);
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();

        int[] selectList = new int[lenCount];
        for(int i = 0; i < lenCount; i++){

        }
        helpAddSubset(0, nums, selectList, resultList);
        return resultList;
    }
    private void helpAddSubset(int curLoc, int[] nums, int[] selectList, List<List<Integer>> curResult){
        if(curLoc == nums.length){
            List<Integer> tempSubset = new ArrayList<>();
            for(int i = 0; i < nums.length; i++){
                if(selectList[i] == 1) tempSubset.add(nums[i]);
            }
            curResult.add(tempSubset);
        }else{
            selectList[curLoc] = 0;
            // 注意这里selectList只是单纯的引用变量, 下面吧curLoc位置置为1又会更改这个类
            // 但是, 在下面更改之后, 已经无所谓了, 需要他是0的场合已经全都执行结束了。妙。
            helpAddSubset(curLoc+1, nums, selectList, curResult);
            selectList[curLoc] = 1;
            helpAddSubset(curLoc+1, nums, selectList, curResult);
        }
    }

    // 比如先加入一个空集让他成为新的子集，然后每遍历一个元素就在原来的子集的后面追加这个值。
    // 追加结果和追加之前的集合, 相当于这个数 存在/不存在 的两种情况, 从头到尾遍历, 即相当于每个数是否存在都考虑了
    // 逐个添加居然也可以得到完整的集合
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(1 << nums.length);
        //先添加一个空的集合
        res.add(new ArrayList<>());
        for (int num : nums) {
            //每遍历一个元素就在之前子集中的每个集合追加这个元素，让他变成新的子集
            for (int i = 0, j = res.size(); i < j; i++) {
                //遍历之前的子集，重新封装成一个新的子集, 注意这里一定是new, 因为res.get(i)是一个引用变量
                List<Integer> list = new ArrayList<>(res.get(i));
                //然后在新的子集后面追加这个元素
                list.add(num);
                //把这个新的子集添加到集合中
                res.add(list);
            }
        }
        return res;
    }

    // 回溯, 完全懂了。http://topurl.cn/4wy
    public List<List<Integer>> subsets3(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
        //走过的所有路径都是子集的一部分，所以都要加入到集合中
        list.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            //做出选择
            tempList.add(nums[i]);
            //递归
            backtrack(list, tempList, nums, i + 1);
            //撤销选择
            tempList.remove(tempList.size() - 1);
        }
    }

    // 纯正的位运算
    public static List<List<Integer>> subsets4(int[] nums) {
        //子集的长度是2的nums.length次方，这里通过移位计算, 因为List最多也就max_value那么长吧, 所以不会超过的
        int length = 1 << nums.length;// 这个数, 即表示了一共有多少个, 同时0~length的二进制表示, 也表示了nums中的组合情况
        List<List<Integer>> res = new ArrayList<>(length);// 直接给长度
        //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
        for (int i = 0; i < length; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < nums.length; j++) {
                //如果数字i的某一个位置是1，就把数组中对
                //应的数字添加到集合
                if (((i >> j) & 1) == 1)
                    list.add(nums[j]);
            }
            res.add(list);
        }
        return res;
    }

    // 和我的结构很像, 但是逻辑不太一样。
    public List<List<Integer>> subsets5(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, nums, new ArrayList<>(), 0);
        return res;
    }

    private void helper(List<List<Integer>> res, int[] nums, List<Integer> list, int index) {
        //终止条件判断
        if (index == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        //每一个节点都有两个分支，一个选一个不选
        //走不选这个分支
        helper(res, nums, list, index + 1);
        //走选择这个分支
        list.add(nums[index]);
        helper(res, nums, list, index + 1);
        //撤销选择
        list.remove(list.size() - 1);
    }

}
